package org.leetcode.easy.leetcode110;

import org.leetcode.TreeNode;

public class Solution
{

    private int DFS (TreeNode root){
        if (root==null){
            return 0;
        }
        int left = DFS(root.left);
        if (left==-1){
            return -1;
        }
        int right = DFS(root.right);
        if (right==-1){
            return -1;
        }
        if (Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right)+1;
    }

    public boolean isBalanced2(TreeNode root){
        if (root==null){
            return true;
        }

        int left = DFS(root.left);
        int right = DFS(root.right);

        if (Math.abs(left-right)>1 || left==-1 || right==-1){
            return false;
        }

        return true;
    }



    public boolean isBalanced(TreeNode root) {

        if (root==null)
        {
            return true;
        }

        int leftDepth = getTreeDepth(root.left);
        int rightDepth = getTreeDepth(root.right);


        if (leftDepth<0 || rightDepth<0)
        {
            return false;
        }

        int abs = Math.abs(leftDepth - rightDepth);
        if (abs>1){
            return false;
        }

        return true;
    }

    private int getTreeDepth(TreeNode root)
    {
        if (root==null)
        {
            return 0;
        }

        int leftDepth = getTreeDepth(root.left);

        if (leftDepth==-1)
        {
            return -1;
        }
        int rightDepth = getTreeDepth(root.right);
        if (rightDepth==-1)
        {
            return -1;
        }
        int abs = Math.abs(leftDepth - rightDepth);
        if (abs>1)
        {
            return -1;
        }else {
            return Math.max(leftDepth,rightDepth)+1;
        }

    }

    public static void main(String[] args) {
//        // 创建叶子节点
//        TreeNode node4Left = new TreeNode(4);
//        TreeNode node4Right = new TreeNode(4);
//
//// 创建第三层的节点，注意null值表示缺少该位置的节点
//        TreeNode node3Left = new TreeNode(3, node4Left, null);
//        TreeNode node3Right = new TreeNode(3, null, node4Right);
//
//// 创建第二层的节点
//        TreeNode node2Left = new TreeNode(2, node3Left, null);
//        TreeNode node2Right = new TreeNode(2, null, node3Right);
//
//// 创建根节点
//        TreeNode root = new TreeNode(1, node2Left, node2Right);


        // 创建各个节点
        TreeNode node5 = new TreeNode(5);
        TreeNode node4 = new TreeNode(4, node5, null);
        TreeNode node3 = new TreeNode(3, node4, null);
        TreeNode node2 = new TreeNode(2, node3, null);
        TreeNode root = new TreeNode(1, node2, null);


        Solution solution = new Solution();
        boolean balanced = solution.isBalanced(root);
        System.out.println(balanced);
    }
}
